Hash-Verfahren

Hash-Verfahren
Hash-Verfahren,
 
ein Speicherungs- und Suchverfahren, bei dem Datensätze gestreut gespeichert und die Adressen von Datensätzen aus den zugehörigen Schlüsseln errechnet werden. Gestreute Speicherung von Datensätzen bedeutet, dass bezüglich irgendeiner Nummerierung der gespeicherten Datensätze nach den Schlüsseln Lücken auftreten. Solche sind in der Praxis nur mit größeren Umständen zu vermeiden, wenn die Menge der möglichen Schlüssel wesentlich größer als die Zahl der Datensätze ist. Eine direkte Adressierung der Datensätze nach den Schlüsseln hätte aber den Nachteil, dass unnötig viele Speicheradressen zur Verfügung gestellt werden müssen. Beim Hash-Verfahren werden nun die Datensätze einem Speicherbereich von passender Größe zugeteilt, und die Adressierung erfolgt indirekt, d. h. über eine Vorschrift, wie sich die Adresse aus den Schlüsseln berechnet. Diese Berechnungsvorschrift heißt Hash-Funktion. Sie wird so entworfen, dass die Adressen schnell zu berechnen sind und sich die Adressen gleichmäßig auf den Speicherbereich verteilen. Dabei ist erlaubt, dass verschiedene Schlüssel zur gleichen Adresse führen. In diesen Fällen (sog. Kollisionen) muss ein Ausweichplatz bereitgestellt und ein Adressverweis dorthin aufgebaut werden. Ein einfaches Verfahren zur Kollisionsvermeidung besteht darin, einen Wert so lange um einen festen Offset zu verschieben, bis ein freier Platz gefunden ist.
 
Die Auflistung aller Funktionswerte (Funktion) einer Hash-Funktion, d. h. aller möglichen Adressierungen, heißt Hash-Tabelle. Sie stellt gewöhnlich eine im Umfang gegenüber der Zahl der Schlüssel beträchtlich reduzierte Menge an Werten dar. Als Beispiel werde ein fünfstelliger Schlüssel aus zwei Ziffern für eine Abteilungsnummer und drei Ziffern für die Angestelltennummer in der Abteilung betrachtet. Das Unternehmen habe die Abteilungen 01, 02 bis 10, die Angestelltennummern laufen bis ca. 50. Bei einfacher Direktumsetzung des Schlüssels auf Adresswerte bräuchte man dann eine fünfstellige Zahl von Adressen, um eine Größenordnung von 100 Datensätzen zu speichern. Als Hash-Funktion könnte man einfach »Angestelltennummer + (Abteilungsnummer - 1) × 50« wählen. Dann benötigt man nur 500 Adressen.
 
Hash-Verfahren finden weitere Anwendung z. B. bei Schachprogrammen, um identische Stellungen, die durch verschiedene Zugfolgen (welche die Schlüssel bilden) erreicht werden, zu identifizieren, oder bei der Datenverschlüsselung.

Universal-Lexikon. 2012.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hash-Kodierung —   [zu engl. to hash »zerhacken«], die Transformation einer Menge von Daten (Schlüsseln) auf eine kleinere Menge von Werten (Adressen) mithilfe einer Hash Funktion (Hash Verfahren). Eine Hash Kodierung, deren Ergebnis keine Rückschlüsse auf die… …   Universal-Lexikon

  • Hash-Funktion — Hash Funktion,   Hash Verfahren …   Universal-Lexikon

  • Hash-Suche — Hash Suche,   ein Suchalgorithmus nach dem Hash Verfahren …   Universal-Lexikon

  • Hash-Tabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hash-Algorithmus — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Wert — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Full-Domain-Hash — (Abkürzung: FDH) ist ein Signaturverfahren aus dem Bereich der Kryptologie. Der Empfänger einer Nachricht kann damit überprüfen, ob die Nachricht, die der Absender an ihn gesandt hat, durch einen Dritten verändert wurde oder nicht. Das Prinzip… …   Deutsch Wikipedia

  • Full Domain Hash — (Abk.: FDH) ist ein Signaturverfahren aus dem Bereich der Kryptologie. Der Empfänger einer Nachricht kann damit überprüfen, ob die Nachricht, die der Absender an ihn gesandt hat, durch einen Dritten verändert wurde oder nicht. Das Prinzip das… …   Deutsch Wikipedia

  • Kryptologische Hash-Funktion — Eine kryptologische Hashfunktion ist eine spezielle Hashfunktion mit weiteren Eigenschaften. Eine kryptologische Hashfunktion sollte zumindest eine Einwegfunktion sein. Eine Hashfunktion ist eine Funktion, die eine Zeichenfolge beliebiger Länge… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”